#include<iostream>
using namespace std;

typedef int ElemType;

struct ListNode
{
    ElemType value;
    ListNode* pNext;
    
    ListNode(ElemType n) : value(n), pNext(NULL){}
};

class CListSort
{
public:
    CListSort(void) : pHead(NULL), elemCnt(0){}
    ~CListSort(void) {delete[] pHead; pHead = NULL;}
    void BuildList(int const* parray, int size);
    void Sort(void);
    void Output(void);
private:
    ListNode* pHead;
    int elemCnt;
};

void CListSort::BuildList(int const* parray, int size)
{
    ListNode* pTemp = NULL;
    ListNode* pPre = NULL;
    for (int i = 0; i < size; i++)
    {
        pTemp = new ListNode(parray[i]);
        
        if (NULL == pPre)
        {
            pHead = pPre = pTemp;
        }
        else
        {
            pPre->pNext = pTemp;
            pPre = pTemp;
        }
    }
    
    elemCnt = size;
}

void CListSort::Sort(void)
{
    ListNode* pPre = NULL;
    ListNode* pStart = pHead;
    pHead = NULL;
    
    while (NULL != pStart)
    {
        ListNode* s = pStart;
        ListNode* q = pStart;
        ListNode* p = q->pNext;
        
        ListNode* r = NULL;
        
        while (NULL != p)
        {
            if (p->value < s->value)
            {
                s = p;
                r = q;
            }
            q = p;
            p = p->pNext;
        }
        
        if (NULL == pPre)
        {
            pHead = pPre = s;
        }
        else
        {
            pPre->pNext = s;
            pPre = s;
        }
        
        if (s == pStart)
        {
            pStart = pStart->pNext;
        }
        else
        {
            r->pNext = s->pNext;
            s->pNext = pStart;
        }
    }
}

void CListSort::Output(void)
{
    ListNode* pNode = pHead;
    
    for (int i = 0; i < elemCnt; i++)
    {
        cout<< pNode->value;
        pNode = pNode->pNext;
        if (i != elemCnt - 1)
        {
            cout<< "->";
        }   
    }
    cout<< "\n";
}

int main(void)
{
    int array[] = {45, 30, 50, 65, 45, 30, 90, 100, 60, 10};
    CListSort cTestList;
    
    cTestList.BuildList(array, sizeof(array) / sizeof(array[0]));
    cTestList.Output();
    cTestList.Sort();
    cTestList.Output();  
    
    system("pause");
}
